package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/22 08:29
 **/
public class Day37_1_Num655_PrintTree {
    class Solution {
        int height = 0;
        List<List<String>> ans;
        public List<List<String>> printTree(TreeNode root) {
            height  = getDepth(root)-1;
            int m = height + 1;
            int n = (int)Math.pow(2,m) - 1;
            ans = new ArrayList<>();
            for(int i = 0; i < m; i++){
                List<String> l = new ArrayList<>();
                for(int j = 0; j < n; j++){
                    l.add("");
                }
                ans.add(l);
            }
            help(root,0,(n - 1) / 2);
            return ans;
        }

        public void help(TreeNode root,int r,int c){
            if(root == null) return;
            ans.get(r).set(c,root.val+"");// +"" 转化为字符串
            help(root.left,r + 1, c - (int)Math.pow(2,height  - r - 1));
            help(root.right,r + 1,c + (int) Math.pow(2,height  - r - 1));
        }

        public int getDepth(TreeNode root){
            if(root==null) return 0;

            return 1+ Math.max(getDepth(root.left),getDepth(root.right));
        }
    }
}